1. Field of the Invention
The present invention relates to interface devices for electrostatic plotters, matrix plotters, matrix television systems and other systems which need matrix or rasterized data to operate. More particularly, the present invention relates to vector to raster converters.
2. History of the Prior Art
In many fields, such as interactive computer-graphics, computers are able to efficiently process data in the form of vectors. A vector is, in effect, a shorthand method of describing a line. Typically, a vector is represented either as two coordinates (the coordinates of its origin and the coordinates of its end point), or as the coordinates of its origin and the change between the origin and the end point in two or three dimensions, depending on whether we are dealing with a surface or a volume. Such a vector description is a shorthand notation as compared to the alternative of providing the coordinates of every identifiable point between the end points of the line.
Obviously, vector notation greatly reduces the amount of data that must be stored in a computer to describe the line. Furthermore, algorithms have been written for computers which efficiently and rapidly process the vector representations.
In addition, vectors may be considered to be mathematically accurate descriptions of lines in that vectors are continuous from endpoint to endpoint.
Output devices exist which can make efficient use of vector data. For example, pen plotters are well known in which the movement of a pen on a sheet of paper can be controlled in two dimensions. Thus, the pen in such a device is directed to the origin of the vector, and then the pen moves either to the coordinates of the end point of the vector or by the amount of change in the dimensions. In this manner, the vector is represented onto the paper. It is a good representation in that it is continuous just like the vector.
However, there are a number of systems which cannot efficiently process data in vector notation. One example of such a system is an electrostatic plotter. Such plotters are capable of simultaneously printing a plurality of selected dots in a particular row across a sheet of paper. The paper then moves by an incremental amount and selected dots in the next row are simultaneously printed. Such printers are generally referred to as line printers in that they print a scan line of dots at a time. In order to print a vector, the printer produces a series of dots which approximate the position of the vector. Thus, there may be any number of dots in a scan line used to represent vector approximations intersecting that scan line. Outputting vectors with a matrix plotter becomes more difficult as the number of vectors increases. For any given row on the output paper, it must be determined where dots should appear so that all of the appropriate vectors are represented.
A key difference, then, between a pen printer and an electrostatic plotter is that the pen printer can output continuous data, while an electrostatic plotter can only output discrete points. The electrostatic plotter must be supplied with data as to which of the plurality of possible discrete dots should be printed. This type of discrete data is referred to as matrix data or "rasterized" data. Other devices which require rasterized data include matrix plotters and raster television systems. A common element of all of these devices or systems is that data is displayed a row at a time.
Thus, for a computer which processes in vector notation to output data to such raster or matrix systems, the data must be rasterized. That is, vector notation must be converted to a raster or matrix format to determine where dots should be located on each scan line of the output device.
Many approaches are known for rasterizing vector data. The following patents relate generally to vector to raster conversion: U.S. Pat. Nos. 3,870,922--Shutoh and 3,821,731--Levine. In the most popular approach, the computer that has been processing the vectors actually does the conversion. First, the computer must define each vector in the plot and clip that portion of any vector which falls outside the area to be printed. Then, the computer must orient the vectors. That is, the computer must determine which end of each vector will appear on the output device first. After all of the vectors are oriented, the computer must order them. That is, the computer must make a list of the vectors in the order in which they will first appear on the output device. Finally, the computer must run through the list of vectors and convert each into a series of coordinates of the dots that approximate the vector.
Tasks such as these are relatively simple repetitive procedures which do not fully utilize the computational resources of a general purpose computer. Furthermore, such simple procedures can be implemented with special purpose hardware at a significant cost reduction and performance improvement.
Systems are presently being marketed where these tasks are performed by a microprocessor system in real time. In such a system, vectors are sent to the microprocessor system in random order. As each vector arrives, it is indexed, for example, using a linked tree-type scheme. The linked tree contains data as to where the next vector which will appear on the plot has been stored.
There are two problems with this approach. The most significant problem is that every vector in the entire plot must be stored, since the last vector sent from the computer to the microprocessor may be the first vector that will be printed. Although such a system does relieve the host computer of performing the entire rasterizing process, the system is still undesirable in that it must include an enormous amount of costly memory. Secondly this approach merely transfers the computational requirements from the host computer to the microprocessor. No processing speed improvements are realized since the microprocessor typically has no more processing capability than the host computer.
To speed the rasterizing process, those skilled in the art have resorted to specialized hardware rather than computers to organize and perform the conversion. In one class of such systems, a host computer generates vectors, orients them (i.e., determines which end of each vector will appear first), and determines which vectors fall within bands on the plot. Furthermore, the host computer divides the plot into equal size bands across the width of the drawing. The band size must be chosen so that the number of vectors appearing in any band does not exceed the capacity of the converting system. The host computer outputs one band of vectors at a time to the converting system where it is stored in vector memory. While the vectors are being loaded, parametric information such as slope and the like are also stored in the vector memory.
As the outputting of raster data begins, each vector in the vector memory is analyzed to determine whether it has any points which fall in the first row to be printed. All such vectors are then flagged as "active" vectors (i.e., those vectors crossing the scan line presently being outputted). The points at which the active vectors cross the scan line being outputted are then calculated, using a slope-intercept approach, and inserted in a scan line buffer. The data in the scan line buffer is then sent to the output device.
Then, the vector list is modified to eliminate those vectors that have been completely printed and to flag those vectors from the vector memory which should become active vectors for the next scan line. This process continues until all of the scan lines in the particular vector band are outputted. At the end of the vector band, all active vectors (i.e., those continuing into the next band) are saved and processed with the next vector band.
The vectors in the next band are then transferred from the host computer to the vector memory and the process described above is repeated.
The system described above has the advantage that the host computer's processing requirements have been reduced; specifically, a majority of the sorting requirements have been distributed and the rasterization process is completely performed by the converting system. However, a number of drawbacks are inherent in this system. Specifically, this system must process the entire vector list for every scan line. For each scan line to be outputted, the coordinates of the dots in that scan line are calculated employing the parametric data stored in the vector memory. The requirement of storing the parametric data greatly enlarges the vector memory, and thus the cost of the system. For example, each vector in the vector memory is described in about 100 bits of data. This is approximately four times the amount of memory needed to simply store the coordinates of the origin of the vector and either the coordinates of the end point or the amount of change between the origin and the end point.
Also, vectors (and not point coordinates) are analyzed to determine whether they fall within a particular scan line to be outputted. The making of this decision requires a relatively large amount of processing for each of the vectors. Thus, this also causes the system to be slow in processing data.
Finally, directed data must be supplied by the host computer to the converting system. That is the vector data must be oriented so that the origin, rather than the end point, of the vectors, will appear first in the plot. This vector manipulation is an additional processing step for the host computer.
The following U.S. patents teach systems similar to that described above in that vectors, and not raster coordinates, are analyzed to determine if the vector falls within a predetermined area or in any case should be processed next: U.S. Pat. Nos. 3,996,585--Hogan et al; 3,812,491--Barraclough et al; 3,893,075 Orban et al; and 3,895,357--Schwartz et al.